COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification = \magstephalf
C00004 00003
C00014 ENDMK
C⊗;
\magnification = \magstephalf
\catcode`|=13
\def|#1|{\hbox{\it#1\/}}
\parindent 0pt
\parskip 0pt
\def\pskip{\penalty-1000\vskip 6pt plus 2pt minus 1pt}
\def\ppskip{\penalty-2000\vskip 10pt plus 3pt minus 2pt}
\def\no(#1){\noindent\hbox to 6em{(#1)\hfill}}
\catcode`⊗=13
\def⊗{\hbox to 2em{}}
\def\IF{\mathop{\hbox{\bf if}}}
\def\THEN{\mathrel{\bf then}}
\def\ELSE{\mathrel{\bf else}}
\def\AND{\mathrel{\bf and}}
\def\OR{\mathrel{\bf or}}
\def\NOT{\mathop{\hbox{\bf not}}}
\def\N{\mathop{\hbox{\bf n}}}
\def\T{\hbox{\tt T}}
\def\NIL{\hbox{\tt NIL}}
\def\.{\mathbin{.}}
\def\A{\mathop{\hbox{\bf a}}}
\def\D{\mathop{\hbox{\bf d}}}
\def\EQ{\mathrel{\bf eq}}
\def\AT{\mathop{\hbox{\bf at}}}
\def\quote#1{\hbox{\sfcode`.=1000\tt#1}}
\def\list#1{\langle#1\rangle}

\centerline{CS 206---Recursive Programming and Proving}
\centerline{Homework 2 Solutions}
\centerline{Thursday, October 27, 1983}


\pskip
{\bf Solutions}:
More than one solution is given for some of the problems; in
such cases the preferred answer is first.

\ppskip
\no(8)$|partition|[u,n]←$\par
$⊗⊗⊗⊗\IF n>|length|\,u\THEN\quote{ERROR}$\par
$⊗⊗⊗⊗\ELSE\IF n=|length|\,u\THEN\list{|mapcar|[|list|,u]}$\par
$⊗⊗⊗⊗\ELSE\IF n=1\THEN\list{\list{u}}$\par
$⊗⊗⊗⊗\ELSE |mapcar|[λv.\,(\list{\A u}\.v),|partition|[\D u,n-1]]$\par
$⊗⊗⊗⊗⊗⊗ *|mapcar|[λv.\,((\A u\.\A v)\.\D v),|partition|[\D u,n]]$\par
\pskip
This is an elegant solution to the problem, although most people didn't
do it this way. Some people had essentially the same idea, but
used named functions instead of the $λ$-expressions. Using named functions
can facilitate a clearer way of working out the solution in some cases.
The idea behind this solution is that a partition of $u$ into $n$ sublists
(the book should have said non-null sublists) either has $\list{\A u}$ as the
first sublist, in which case the remainder is a partition of $\D u$ into
$n-1$ sublists, or it has a first sublist with more than one member; in
that case removing $\A u$ from the first sublist creates one of the
partitions of $\D u$ into $n$ sublists, so we can reverse the process by
``splicing'' $\A u$ into each member of $|partition|[\D u,n]$.
Several people did not include the proper level of lists in the base
cases of the recursion; this is important to make the function work
correctly.

\pskip
Another approach was to take initial segments of $u$ one at a time, and
add them to each member of the rest of $u$, partitioned into $n-1$
sublists, with appropriate termination cases.

\pskip
When you detect an error case, it is not necessary to do anything fancy.
In this case, returning the atom \quote{ERROR} is quite reasonable, since
we never expect the output of the function to be an atom.  In fact,
there might be a version of |partition| which calls itself recursively and
expects to get \quote{ERROR} back in some cases.

\pskip
$⊗⊗⊗|testpart|[p,u]←\N p\OR u=|appendlist|[\A p]\AND|testpart|[\D p,u]$\par
\vskip 2pt
$⊗⊗⊗|appendlist|[v]←\IF\N v\THEN\NIL\ELSE \A v*|appendlist|[\D v]$\par

\ppskip
\no(9)$|mirror|\,x←$\par
$⊗⊗⊗⊗\IF\AT x\THEN x$\par
$⊗⊗⊗⊗\ELSE (|mirror|\,\D x)\.(|mirror|\,\A x)$\par

\ppskip
\no(10)$|occur|[x,y]←$\par
$⊗⊗⊗⊗\IF\AT y\THEN x=y$\par
$⊗⊗⊗⊗\ELSE |occur|[x,\A y]\OR |occur|[x,\D y]$\par
\pskip
It isn't necessary to write $\IF\AT y\THEN(\IF x=y\THEN\T\ELSE\NIL)$, since
this is equivalent to the above.

\ppskip
\no(11)$|multiplicity|[x,y]←$\par
$⊗⊗⊗⊗\IF\AT y\THEN(\IF x=y\THEN 1\ELSE 0)$\par
$⊗⊗⊗⊗\ELSE|multiplicity|[x,\A y]+|multiplicity|[x,\D y]$\par

\ppskip
\no(12)$|ispath|[p,x]←$\par
$⊗⊗⊗⊗\N p\OR\NOT\AT x\AND$\par
$⊗⊗⊗⊗⊗⊗(\IF\A p=\quote{A}\THEN|ispath|[\D p,\A x])$\par
$⊗⊗⊗⊗⊗⊗(\ELSE|ispath|[\D p,\D x])$\par
\pskip
We could use |eq| instead of |equal| to save a few microseconds of computer
time.  The function above does no error checking; it assumes that $p$
is a list containing only \quote{A}'s and \quote{D}'s.

\ppskip
\no(13)$|depth|\,x←$\par
$⊗⊗⊗⊗\IF\AT x\THEN 0$\par
$⊗⊗⊗⊗\ELSE 1+|max|[|depth|\,\A x,|depth|\,\D x]$\par
\pskip
Most versions of LISP have |max| as a built-in function, but if you
didn't know that, you could include the definition
\pskip
$⊗⊗⊗|max|[m,n]←\IF m>n\THEN m\ELSE n$

\vfill\end